/*-------------------------------------------------------------------------*/
/**
  @file		coarsen.c
  @author	Renaud Wanchoor
  @date	July 2004
  @version	$Revision: 2.11 $
  @brief	coarsening phase
  
*/
/*--------------------------------------------------------------------------*/
#include "pagrid.h"

#define MAXVWGT MAXVWGT1 /**< \brief compute the maximum weight of two matched vertices */
#define MAXVWGT1(vwgtsum,nvtxs,npro) (nvtxs/2 < npro?INFINITY:1.5 * ((double)vwgtsum/npro))
#define MAXVWGT2(vwgtsum,nvtxs,npro) (nvtxs/2 < npro?INFINITY:1.5 * ((double)vwgtsum/(MAX(nvtxs/2,npro))))
/**
 * \brief generate a sequence of coarse graph
 *
 * Coarse down the graph until the number of vertices
 * is equal to the number of edges
 *
 * \param graph initial graph structure pointer
 * \param grid grid structure pointer
 * \param info partition info
 * \param ctrl input parameter
 *     - PartInfoType::CType : matching scheme
 *     - PartInfoType::WType : edge weight
 *
 * \return coarsest graph
 */

GraphType* Coarsen(GraphType *graph, GridType *grid, PartInfoType *info)
{
  int i;
  Mem	  mem;
  CoaCtrl coactrl;
  
  int     level   = 0;
  int     nvtxs   = graph->nvtxs;
  int*     vwgt   = graph->vwgt;
  int     npro    = grid->npro;
  int   vwgtsum   = 0;
  
    
  /*Initialization*/
  MEM_Init(&mem);
  MEM_Need(&mem,2*nvtxs,int);
  MEM_Allocate(&mem);

  coactrl.g         = graph;
  coactrl.npro      = npro;
  coactrl.label     = MEM_Request(&mem,nvtxs,int);
  coactrl.randguide = 1;
  coactrl.guide     = MEM_Request(&mem,nvtxs,int);
  coactrl.info      = info;

  for(i=0;i<nvtxs;i++)
    vwgtsum += vwgt[i];

  coactrl.maxvwgt = MAXVWGT(vwgtsum,nvtxs,npro);
  
  /* do while number of vertices is same as the number of processors*/
  while (coactrl.g->nvtxs > npro * 5) {
    
    /* do matching */
    switch(info->CType){
    case IO_MATCH_LAM:
      coactrl.g = LAM(&coactrl);
      break;
    case IO_MATCH_RM:
      coactrl.g = Rm(&coactrl);
      break;
    case IO_MATCH_MWM:
      coactrl.g = MWM(&coactrl);
      break;
    case IO_MATCH_HEM:
      coactrl.g = Hem(&coactrl);
      break;
    case IO_MATCH_SHEM:
    default:
      coactrl.g = MHem(&coactrl);
    }

    if(nvtxs == coactrl.g->nvtxs)
      coactrl.maxvwgt *= 2;
    nvtxs = coactrl.g->nvtxs;

    level++;
  }
  
  info->level = level;
  
  MEM_Free(&mem);

  return coactrl.g;
}
